package com.ls.que96_100;

import com.ls.utils.TreeNode;

import java.util.ArrayList;
import java.util.List;

/**
 * @author ：ls
 * @date ：2022/3/16 14:12
 * @description：...
 */
public class RecoverTree {
    public static void recoverTree(TreeNode root) {
        List<TreeNode> nodes = new ArrayList<>();
        orderTravel(root, nodes);

        TreeNode t1=null, t2=null;
        int i=0;
        for (TreeNode node : nodes){
            if (i==0){
                if (node.val > nodes.get(i+1).val)
                    t1 = node;
            }else if (i==nodes.size()-1){
                if (node.val < nodes.get(i-1).val) {
                    t2 = node;
                }
            }else {
                if ((node.val > nodes.get(i-1).val && node.val > nodes.get(i+1).val) ||(node.val < nodes.get(i-1).val && node.val < nodes.get(i+1).val)){
                    if (t1 ==null)
                        t1 = node;
                    else t2 = node;
                }
            }
            i+=1;
        }

        int a = t1.val;
        t1.val = t2.val;
        t2.val = a;
    }

    public static void orderTravel(TreeNode node, List<TreeNode> temp){
        if (node.left!=null)
            orderTravel(node.left, temp);

        temp.add(node);

        if (node.right!=null)
            orderTravel(node.right, temp);
    }

    public static void main(String[] args) {
        TreeNode t1 = new TreeNode(3);
        TreeNode t2 = new TreeNode(1);
        TreeNode t3 = new TreeNode(4);
        TreeNode t4 = new TreeNode(2);
        t1.left = t2;
        t1.right = t3;
        t2.left = null;
        t2.right = null;
        t3.left = t4;
        t3.right = null;
        t4.left = null;
        t4.right = null;

        recoverTree(t1);
    }
}
